package com.mgq.algorithm.array;

import java.util.Arrays;

/**
 * @author MaGuangQi
 * @date 2021-12-28 10:02
 **/
public class QuickSort {
    public static void main(String[] args) {
        //
        int[] array = {3, 6, 2, 5, 7, 5};
        quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(int[] array, int L, int R) {
        if (L < R) {
            //随机 R-L+1返回元素的个数  (Math.random()*(R-L+1)) 返回长度内任意值.
            //把array上,任意一个值和数组最后的值交换
            //swap(array, (int) (L+(Math.random()*(R-L+1))),R);
            swap(array, (int) (L+(Math.random()*(R-L+1))),R);
            //交换完之后做partition. partition返回的是等于 array[R]的值下标左边界和右边界
            //partition还有个功能,就是将<num的数放在数组的左边,=num的数放在中间,>num放在数组的右边
            //举例:
            //3,6,3,5,7,5 -num=5
            //0 1 2 3 4 5  下标
            //partition后
            //3 3 5 5 6 7
            //0 1 2 3 4 5  下标
            //返回的值是=5的左边界下标和右边界下标.(真正快的原因就是中间=的个数,因为=的个数越多,下次就不用排中间的了
            int[] p = partition(array, L, R);
            int leftBord = p[0] - 1; //<区的右边界
            int rightBord=p[1]+1;// >区的左边界
            quickSort(array,L,leftBord);
            quickSort(array,rightBord,R);
        }
    }

    private static void swap(int[] array, int i, int j) {
        System.out.println("i的值是:"+i+","+array[i]+",j的值是:"+j+","+array[j]);
        System.out.println("交换前:"+Arrays.toString(array));
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
        System.out.println("交换后:"+Arrays.toString(array));
    }

    /**
     * 以array[R]作为划分, array[<arr[R]   = arr[R]    >arr[R]]
     * @param array
     * @param L
     * @param R
     * @return
     */
    private static int[] partition(int[] array, int L, int R) {
        int less=L-1; //<区的右边界(小于区向右移动)
        int more=R; //>区的左边界(划分区域的右边界的左边界(右边界向左移动)
        //<区和>区不重合的时候
        while (L < more) {
            //
            if (array[L] < array[R]) { //当前数小于划分数
                System.out.println("less:"+less);
                System.out.println("more:"+more);
                swap(array,++less,L++); //当前值和我小于区里面的下一个值交换,同时小于区右移一位
            } else if (array[L] > array[R]) { //当前数大于划分数
                swap(array, --more, L); //指针不动,右边界左移,交换
            } else {
                L++;
            }
        }
        //这里排完左中右的数，就把more位置上的数（也就是>基数区域的第一个数）和最后R位置上的基数换回来
        swap(array,more,R);
        //为什么这里是less+1,more
        //因为上一步把R和more又换回来， 中间数多了一个，more位置上的数也就从>区第一个数变成了=区最后一个数
        return new int[]{less+1,more};
    }
}
